/**
 * Copyright 2012 Roger Cockshutt
 * krakenbrau@gmail.com
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.googlecode.parallelrl.util;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Roger Cockshutt
 *
 */
public class Tree2D {

	private Integer nodeCapacity = 4;
	private Box2D boundingBox;
	private List<Point2D> points;
	private Tree2D[] quadrants = new Tree2D[4];
	
	public Tree2D(Box2D boundary) {
		points = new ArrayList<Point2D>(nodeCapacity);
		boundingBox = boundary;
		Arrays.fill(quadrants, null);
	}
	
	public Point2D getPointForHash(Long hash) {
		String hStr = hash.toString();
		if (hStr.length() == 1) {
			return points.get(Integer.valueOf(hStr.substring(0, 1)) - 1);
		}
		return quadrants[Integer.valueOf(hStr.substring(0, 1)) - 1].getPointForHash(Long.valueOf(hStr.substring(1)));
	}
	
	public Boolean containsPoint(Point2D p) {
		if (getHashForPoint(p) != null) {
			return true;
		}
		return false;
	}
	
	public Long getHashForPoint(Point2D p) {
		Long hash = null;
		if (boundingBox.containsPoint(p)) {
			if (points.contains(p)) {
				hash = (long) (points.indexOf(p) + 1);
			} else {
				if (quadrants[0] != null) {
					hash = quadrants[0].getHashForPoint(p);
					if (hash != null) {
						hash = Long.valueOf("1" + hash.toString());
						return hash;
					}
					hash = quadrants[1].getHashForPoint(p);
					if (hash != null) {
						hash = Long.valueOf("2" + hash.toString());
						return hash;
					}
					hash = quadrants[2].getHashForPoint(p);
					if (hash != null) {
						hash = Long.valueOf("3" + hash.toString());
						return hash;
					}
					hash = quadrants[3].getHashForPoint(p);
					if (hash != null) {
						hash = Long.valueOf("4" + hash.toString());
						return hash;
					}
				}
			}
		}
		return hash;
	}
	
	public Boolean insert(Point2D p) {
		Boolean inserted = false;
		if(boundingBox.containsPoint(p)) {
			if (nodeCapacity > 0) {
				points.add(p);
				inserted = true;
				nodeCapacity--;
			} else {
				if (quadrants[0] == null) {
					subdivide();
				}
				if (quadrants[0].insert(p)
						|| quadrants[1].insert(p)
						|| quadrants[2].insert(p)
						|| quadrants[3].insert(p)) {
					inserted = true;
				}
			}
		}
		return inserted;
	}
	
	
	
	public Point2D remove(Point2D p) {
		Point2D rPt = null;
		if (boundingBox.containsPoint(p)) {
			if (points.contains(p)) {
				rPt = points.remove(points.indexOf(p));
				nodeCapacity++;
			} else {
				if (quadrants[0] != null) {
					for (int i = 0; i < quadrants.length && rPt == null; i++) {
						rPt = quadrants[i].remove(p);
					}
				}
			}
		}
		return rPt;
	}
	
	private void subdivide() {
		Integer upY, leftX, downY, rightX, halfY, halfX;
		Point2D upLeftCenter, upRightCenter, downLeftCenter, downRightCenter, newHalfDim;
		Box2D upLeftBounds, upRightBounds, downLeftBounds, downRightBounds;
		
		upY = boundingBox.center.y - (boundingBox.halfDimension.y / 2);
		leftX = boundingBox.center.x - (boundingBox.halfDimension.x / 2);
		downY = boundingBox.center.y + (boundingBox.halfDimension.y / 2);
		rightX = boundingBox.center.x + (boundingBox.halfDimension.x / 2);
		halfY = (boundingBox.halfDimension.y / 2) + (boundingBox.halfDimension.y % 2);
		halfX = (boundingBox.halfDimension.x / 2) + (boundingBox.halfDimension.x % 2);
		
		upLeftCenter = new Point2D(upY, leftX);
		upRightCenter = new Point2D(upY, rightX);
		downLeftCenter = new Point2D(downY, leftX);
		downRightCenter = new Point2D(downY, rightX);
		newHalfDim = new Point2D(halfY, halfX);
		
		upLeftBounds = new Box2D(upLeftCenter, newHalfDim);
		upRightBounds = new Box2D(upRightCenter, newHalfDim);
		downLeftBounds = new Box2D(downLeftCenter, newHalfDim);
		downRightBounds = new Box2D(downRightCenter, newHalfDim);
		
		quadrants[0] = new Tree2D(upLeftBounds);
		quadrants[1] = new Tree2D(upRightBounds);
		quadrants[2] = new Tree2D(downLeftBounds);
		quadrants[3] = new Tree2D(downRightBounds);
		
		for (int q = 0; q < 4; q++) {
			for (int i = 0; i < points.size(); i++) {
				if (quadrants[q].insert(points.get(i))) {
					points.remove(i);
					i--;
				}
			}
		}
	}
	
	public List<Point2D> queryRange(Box2D range) {
		List<Point2D> queriedPoints = new ArrayList<>();
		if (boundingBox.intersectsBox(range)) {
			for (Point2D p : points) {
				if (range.containsPoint(p)) {
					queriedPoints.add(p);
				}
			}
			if (quadrants[0] != null) {
				queriedPoints.addAll(quadrants[0].queryRange(range));
				queriedPoints.addAll(quadrants[1].queryRange(range));
				queriedPoints.addAll(quadrants[2].queryRange(range));
				queriedPoints.addAll(quadrants[3].queryRange(range));
			}
		}
		return queriedPoints;
	}

}
